#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 5e6 + 5;

int n, q;
bool cut(string& s, string& t, string& x, string& y, string& z) {
  int n = s.size();
  int l = 0, r = n - 1;
  while (l < n && s[l] == t[l]) l++;
  if (l == n) return false;
  while (r >= 0 && s[r] == t[r]) r--;
  x = s.substr(0, l + 1), z = s.substr(r);
  y = s.substr(l, r + 1 - l) + t.substr(l, r + 1 - l);
  reverse(x.begin(), x.end());
  return true;
}
int tr1[N][26], rt[N], tr2[N][26], sz[N];
vector<string> a[N];
map<string, int> id;
static int n1 = 0, n2 = 0;
int new_node1() { return ++n1; }
void insert1(int& rt, string& x, string& z) {
  if (!rt) rt = new_node1();
  int p = rt;
  for (char c : x) {
    int ch = c - 'a';
    if (!tr1[p][ch]) tr1[p][ch] = new_node1();
    p = tr1[p][ch];
  }
  a[p].push_back(z);
}
int query1(int p, string& x) {
  for (char c : x) {
    int ch = c - 'a';
    if (!tr1[p][ch]) break;
    p = tr1[p][ch];
  }
  return p;
}
int new_node2(int p) {
  n2++;
  rep(i, 0, 25) tr2[n2][i] = tr2[p][i];
  sz[n2] = sz[p];
  return n2;
}
void insert2(int& rt, string& z) {
  rt = new_node2(rt);
  int p = rt;
  for (char c : z) {
    int ch = c - 'a';
    tr2[p][ch] = new_node2(tr2[p][ch]);
    p = tr2[p][ch];
  }
  sz[p]++;
}
int query2(int p, string& z) {
  int res = 0;
  for (char c : z) {
    int ch = c - 'a';
    p = tr2[p][ch];
    if (!p) break;
    res += sz[p];
  }
  return res;
}
void dfs(int u, int fu) {
  if (!u) return;
  rt[u] = new_node2(rt[fu]);
  for (auto& s : a[u]) {
    insert2(rt[u], s);
  }
  rep(i, 0, 25) dfs(tr1[u][i], u);
}
void insert(string& x, string& y, string& z) { insert1(id[y], x, z); }
int query(string& x, string& y, string& z) {
  int p = id[y];
  if (!p) return 0;
  p = query1(p, x);
  return query2(rt[p], z);
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> q;
  rep(i, 1, n) {
    string s, t, x, y, z;
    cin >> s >> t;
    if (!cut(s, t, x, y, z)) continue;
    insert(x, y, z);
  }
  for (auto now : id) dfs(now.second, 0);
  while (q--) {
    string s, t;
    cin >> s >> t;
    if (s.size() != t.size())
      cout << 0 << endl;
    else {
      string x, y, z;
      cut(s, t, x, y, z);
      cout << query(x, y, z) << endl;
    }
  }
  return 0;
}